#!/usr/bin/python2.4
#
# Copyright 2010 Google Inc.

# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0

# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.


"""An example of how to put the framework to use.

An entry point for the optimisation. This module takes the following inputs:

   1) tests : a list of test target names
   2) matrix : a list of numpy.ndarrays that describes the coverage relation
   3) metadata : a dictionary that maps test target names to Aggregate
      objects - refer to sponge_dremel module for Aggregate object
   4) timelimit : the cpu time budget for the test selection (in seconds).
      if omitted, the module takes half the amount of total cpu time required
      by all test targets in tests

After obtaining the Pareto-front from the TwoArchive algorithm, the module
searches the solution set in order to find a set of test targets that:

1) does not require more cpu time than timelimit, and
2) achieves the highest dependency/past fault coverage while satisfying 1)

If there is no solution within the budget, the module keeps increasing the
timelimit by 60 seconds until it finds a solution. Increasing the limit is cheap
because the optimization algorithm creates a spectrum of solutions in different
time ranges.

The module's implementation is currently tied to Problem4ObjMaxReturnTime.
If a new problem definition is used, the suggestion procedure needs to be
updated accordingly.

This module also configures the TwoArchive algorithm. Only two parameters
are of interest: populationSize and maxEvaluations. Higer numbers will result
in longer time for optimisation. Recommended value for archiveSize is double
the size of the population.

"""

__author__ = 'ntrolls@gmail.com (Shin Yoo), robni@google.com (Robert Nilsson)'

import os

import datasource
import genetic_operators
import problem
import twoarchive
import persistence


def Optimizer(tests, matrix, metadata, config, timelimit=None):
  """Provides a centralised interface to optimisation."""
  ds = datasource.DataSource()
  ds.Initialise(tests, matrix, metadata)

  ## we use the basic 2-objective formulation: cost and coverage
  prob = problem.Problem2Obj(ds)

  # configuring the Two-Archive multi-objective evolutionary algorithm
  # lower maxEvaluations will result in shorter execution time, but may
  # compromise precision; selection, crossover and mutation do not need
  # fiddling for now
  algorithm = twoarchive.TwoArchive(prob)
  algorithm.properties['maxEvaluations'] = 25000
  algorithm.properties['populationSize'] = 100
  algorithm.properties['archiveSize'] = 200
  algorithm.properties['selection'] = genetic_operators.TwoArchiveSelection()
  algorithm.properties['crossover'] = genetic_operators.SinglePointCrossover()
  mu_rate = 1 / float(ds.numberoftests)
  algorithm.properties['mutation'] = genetic_operators.BitFlipMutation(mu_rate)

  results = algorithm.Execute()
  results_cache_filename = os.path.join(config.temp_dir, 'results_%s_%s.txt' %
                                        (config.client_id, config.session_id))
  results_cache = persistence.PersistenceHelper(results_cache_filename)
  results_cache.WriteData(results)
  
  # if, somehow, the algorithm returns no solution, do not go into the 
  # suggestion loop (as it will cause an infinite loop)
  if not results:
    return None, None, False

  # if there are solutions in the result, suggest one set of tests
  if timelimit:
    return SuggestTestsWithinLimit(results, ds, timelimit)
  else:
    return SuggestTests(results, ds)


def EstimateRuntime(result):
  return (result.GetObjectiveValueByName('cost') +
          result.GetObjectiveValueByName('max_cost')) / 2


def SuggestTestsWithinLimit(results, data_source, timelimit):
  tests, cost, status = PickTestsWithinLimit(results, data_source, timelimit)
  # if no set exists within the time limit, we increase the limit by
  # 1 minute (60 seconds) until we find one
  while not tests:
    timelimit += 60
    tests, cost, status = PickTestsWithinLimit(results, data_source, timelimit)
  return tests, cost, status


def PickTestsWithinLimit(results, data_source, timelimit):
  """Select a solution that meets the timelimit from results."""
  ## okay, we have the result from the optimisation
  ## now we actually need to pick one set to recommend!

  ## we select the set with highest coverage
  ## whose cost is under the limit
  best_solution = None
  best_coverage = 0
  best_fault_coverage = 0
  for result in results:
    estimated_time = result.GetObjectiveValueByName('cost')
    if estimated_time < timelimit:
      current_coverage = abs(result.GetObjectiveValueByName('coverage'))
      current_fault_coverage = abs(
          result.GetObjectiveValueByName('past_fault_cov'))
      if current_coverage > best_coverage:
        best_coverage = current_coverage
        best_solution = result
      elif (current_coverage == best_coverage and
            current_fault_coverage > best_fault_coverage):
        best_fault_coverage = current_fault_coverage
        best_solution = result
  if best_solution:
    tests = []
    for i in xrange(len(best_solution.gene)):
      if best_solution.gene[i]:
        tests.append(data_source.testnames[i])
    return tests, best_solution.GetObjectiveValueByName('cost'), True
  else:
    return None, None, False


def SuggestTests(results, data_source):
  # when there is no time limit given, we set it to the 50% of the cost
  # required to execute all the tests we considered
  limit = sum(data_source.costs) / 2
  return SuggestTestsWithinLimit(results, data_source, limit)
